﻿using System;
using System.Collections.Generic;
using System.Text;

namespace LeetcodeTest._100._30
{
    public class Leetcode22
    {
        /*
         22. Generate Parentheses

         Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

         */
        public IList<string> GenerateParenthesis(int n)
        {
            List<string> listString = new List<string>();
            solve(0, 2 * n, 0, 0, "", listString);
            return listString;
        }

        /// <summary>
        /// 一直没思路。。网上找了代码也没搞懂。。
        /// </summary>
        /// <param name="dep"></param>
        /// <param name="maxDep"></param>
        /// <param name="leftNum"></param>
        /// <param name="leftNumTotal"></param>
        /// <param name="s"></param>
        /// <param name="listString"></param>
        void solve(int dep, int maxDep, int leftNum, int leftNumTotal, string s, List<string> listString)
        {
            if (leftNumTotal * 2 > maxDep)
                return;

            if (dep == maxDep)
            {
                listString.Add(s);
                return;
            }

            for (int i = 0; i < 2; i++)
            {
                if (i == 0)
                {
                    solve(dep + 1, maxDep, leftNum + 1, leftNumTotal + 1, s + '(', listString);
                }
                else
                {
                    if (leftNum > 0)
                        solve(dep + 1, maxDep, leftNum - 1, leftNumTotal, s + ')', listString);
                }
            }
        }
    }
}
